/*
 * @lc app=leetcode.cn id=480 lang=java
 *
 * [480] 滑动窗口中位数
 */

import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Map;

// @lc code=start
class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        // 优先级队列  大根堆 + 小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((a,b)->(a<b)?1:-1);
        Map<Integer, Integer> mp = new HashMap<>();
        int n = nums.length;
        double[] res = new double[n-k+1];

        for(int i = 0; i < k; i++) {
            maxHeap.add(nums[i]);
        }
        for(int i = 0; i < k/2; i++) {
            minHeap.add(maxHeap.poll());
        }

        if(k %2 == 0) {
            res[0] = ((long)minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            res[0] = maxHeap.peek();
        }

        for (int i = k; i < n; i++) {
            int del = nums[i - k], add = nums[i];
            int dif = 0;
            if (del <= maxHeap.peek()) dif--;
            else dif++;
            mp.put(del, mp.getOrDefault(del, 0) + 1);
            if (add <= maxHeap.peek()) {
                maxHeap.add(add);
                dif++;
            } else {
                minHeap.add(add);
                dif--;
            }
            //dif = -2 0 2
            if (dif > 0) {
                //大顶堆个数多2,弹出2个平衡
                minHeap.add(maxHeap.poll());
            } else if (dif < 0) {
                maxHeap.add(minHeap.poll());
            }
            //堆顶删除
            while (mp.getOrDefault(maxHeap.peek(), 0) > 0) { //不用判断堆是否为空 因为为空弹出null 获得的为0
                mp.put(maxHeap.peek(), mp.get(maxHeap.peek()) - 1);
                maxHeap.poll();
            }
            //注意应该先让大根堆删除
            while (mp.getOrDefault(minHeap.peek(), 0) > 0) {
                mp.put(minHeap.peek(), mp.get(minHeap.peek()) - 1);
                minHeap.poll();
            }
            if (k % 2 == 0) res[i - k + 1] = ((long)minHeap.peek() +  maxHeap.peek()) * 0.5;
            else res[i - k + 1] = maxHeap.peek();
        }
        return res;
    }
}
// @lc code=end

